% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx} 


\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large Lab 4 -- Solution\\ \vspace{0.2em}
        {\bf Search Algorithms}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo\\
        \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Le Do Thai	}
\newcommand{\lastnamethree}{Binh   }
\newcommand{\matriculationnumberthree}{114910}

\begin{document}
\pagestyle{plain}
\header


\textbf{Task 1}\\\\
(a) DFS. We assume that successors(n) returns list of successors sorted by node number. In this case algorithms performs the following: 

\begin{center}
    \begin{tabular}{ | p{2cm} | p{4cm} | p{8cm} |}
    
    \hline  \textbf{Iteration }& \textbf{Open} & \textbf{Closed}  \\
    \hline  1 & 0 &   empty \\
    \hline  2 & 13, 15 & 0   \\ 
    \hline  3 & 13, 12, 16 & 0, 15   \\ 
    \hline  4 & 13, 12, 11 & 0, 15, 16   \\ 
    \hline  5 & 13, 12, 10 & 0, 15, 16, 11   \\ 
    \hline  6 & 13, 12, 9 & 0, 15, 16, 11, 10   \\
    \hline  7 & 13, 12, 8 & 0, 15, 16, 11, 10, 9   \\
    \hline  8 & 13, 12, 3, 5, 6, 7, 14  & 0, 15, 16, 11, 10, 9, 8   \\
    \hline  9 & 13, 12, 3, 5, 6, 7  & 0, 15, 16, 11, 10, 9, 8, 14   \\
    \hline  10 & 13, 12, 3, 5, 6  & 0, 15, 16, 11, 10, 9, 8, 14, 7   \\
    \hline  11 & 13, 12, 3, 5  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6  \\
    \hline  12 & 13, 12, 3, 4  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6, 5  \\
    \hline  13 & 13, 12, 3  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6, 5, 4  \\
    \hline  14 & 13, 12, 2  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6, 5, 4, 3  \\
    \hline  15 & 13, 12, 1  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6, 5, 4, 3, 2  \\
    \hline  16 & 13, 12  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6, 5, 4, 3, 2, 1  \\
    \hline  17 & 13  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6, 5, 4, 3, 2, 1, 12  \\
    \hline  18 & empty  & 0, 15, 16, 11, 10, 9, 8, 14, 7, 6, 5, 4, 3, 2, 1, 12, 13  \\
    \hline 
    \end{tabular}
\end{center}
Thus elements are expanded in the order(height) 0(0), 15(1), 16(2), 11(3), 10(4), 9(5), 8(6), 14(7), 7(8), 6(9), 5(10), 4(11), 3(12), 2(13), 1(14), 12(15), 13(16)\\\\
(b) BFS. We assume that successors(n) returns list of successors sorted by node number. In this case algorithms performs the following: 
\begin{center}
    \begin{tabular}{ | p{2cm} | p{4cm} | p{8cm} |}
    
    \hline  \textbf{Iteration }& \textbf{Open} & \textbf{Closed}  \\
    \hline  1 & 0 &   empty \\
    \hline  2 & 13, 15 &   0 \\
    \hline  3 & 15, 1, 3, 14 &   0, 13 \\
    \hline  4 & 1, 3, 14, 12, 16 &   0, 13, 15 \\
    \hline  5 & 3, 14, 12, 16, 2 &   0, 13, 15, 1 \\
    \hline  6 & 14, 12, 16, 2, 4, 8  &   0, 13, 15, 1, 3 \\
    \hline  7 & 12, 16, 2, 4, 8  &   0, 13, 15, 1, 3, 14 \\
    \hline  8 & 16, 2, 4, 8, 9, 11  &   0, 13, 15, 1, 3, 14, 12\\
    \hline  9 & 2, 4, 8, 9, 11  &   0, 13, 15, 1, 3, 14, 12, 16\\
    \hline  10 &  4, 8, 9, 11  &   0, 13, 15, 1, 3, 14, 12, 16, 2\\
    \hline  11 &  8, 9, 11, 5  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4\\
    \hline  12 &  9, 11, 5, 6, 7  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4, 8\\
    \hline  13 &  11, 5, 6, 7, 10  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4, 8, 9\\
    \hline  14 &  5, 6, 7, 10  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4, 8, 9, 11\\
    \hline  15 &  6, 7, 10  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4, 8, 9, 11, 5\\
    \hline  16 &  7, 10  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4, 8, 9, 11, 5, 6\\
    \hline  17 &  10  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4, 8, 9, 11, 5, 6, 7\\
    \hline  18 &  empty  &   0, 13, 15, 1, 3, 14, 12, 16, 2, 4, 8, 9, 11, 5, 6, 7, 10\\
    \hline 
    \end{tabular}
\end{center}
Thus elements are expanded in the order(height) 0(0), 13(1), 15(2), 1(3), 3(4), 14(5), 12(6), 16(7), 2(8), 4(9), 8(10), 9(11), 11(12), 5(13), 6(14), 7(15), 10(16)\\\\

(c) Uniform cost search. 
\begin{center}
    \begin{tabular}{ | p{2cm} | p{4cm} | p{8cm} |}
    
    \hline  \textbf{Iteration }& \textbf{Open} & \textbf{Closed}  \\
    \hline  1 & 0 &   empty \\
    \hline  2 & 13(3), 15(11)  &   0 \\
    \hline  3 & 1(5), 14(11), 15(11), 3(24)  &   0, 13(3) \\
    \hline  4 & 2(9), 14(11), 15(11), 3(24)  &   0, 13(3), 1(5) \\
    \hline  5 & 14(11), 15(11), 3(24)  &   0, 13(3), 1(5), 2(9) \\
    \hline  6 & 15(11), 12(21), 3(24), 8(29)  &   0, 13(3), 1(5), 2(9), 14(11) \\
    \hline  7 & 16(12), 12(21), 3(24), 8(29)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11) \\
    \hline  8 & 12(21), 3(24), 8(29), 11(32)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12) \\
    \hline  9 & 3(24), 8(29), 11(32), 9(36)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21) \\
    \hline  10 & 8(29), 11(32), 9(36), 4(37)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24) \\
    \hline  11 & 11(32), 9(36), 5(35), 4(37), 7(41), 6(53)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29) \\
    \hline  12 & 5(35), 9(36), 4(37), 10(49), 7(41), 6(53)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32) \\
    \hline  13 & 9(36), 4(37), 10(49), 7(41), 6(53)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32),  5(35) \\
    \hline  14 & 4(37), 10(49), 7(41), 6(53)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32),  5(35), 9(36) \\
    \hline  15 & 10(49), 7(41), 6(53)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32),  5(35), 9(36), 4(37) \\
    \hline  16 & 7(41), 6(53)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32),  5(35), 9(36), 4(37), 10(49) \\
    \hline  17 & 6(53)  &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32),  5(35), 9(36), 4(37), 10(49), 7(41) \\
    \hline  18 & empty &   0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32),  5(35), 9(36), 4(37), 10(49), 7(41), 6(53)  \\
    \hline 
    \end{tabular}
\end{center}
Thus elements are expanded in the order 0, 13(3), 1(5), 2(9), 14(11), 15(11), 16(12), 12(21), 3(24), 8(29), 11(32), 5(35), 9(36), 4(37), 10(49), 7(41), 6(53)\\\\

\textbf{Task 2}\\\\
Since BFS differs from Uniform cost search only in terms of open list data structure it's clear that if they behave in the same way the algorithms work the same as well.
\\\\For BFS queue is used, which means FILO strategy is used and no manipulation on adding an element is performed. 
\\\\Unifrom cost search uses priority queue which means there will be sorting of all elements of the queue as soon as new element is added.
\\\\So, if all edges cost 1, every result of successors(n) call throught execution will return nodes with weights (weight(n) + 1). It means the order of elements will only depend on when operator add was called (successors go after parents) as in a simple queue.
\\\\As was mentioned above, if data structures behave the same we deal with the same behaviour of algorithms. It also implies that BFS is a special case of uniform cost search.\\
\\
\textbf{Task 5}\\
a)\\
No, for example: \\
n1->n2 = 10 \\
n2->n3 = 10 n2->n4 = 30 \\
n3->n5 = 15 \\
n4->n5 = 30 \\
n1 is start node and n5 is goal node \\
path1 = optimalPath(n1, n5) = n1->n2->n3->n5 = 5 \\
optimalPath(n2, n5) = n2->n4->n5 = 0 \\
path1 is optimal but not all subpath of path1 is optimal(path from n2 to n5)\\
b)\\
Solution with minimal cost: n6->n7->n8->n14->n12->n15->n0\\
Cost = 19 - 7 = 12\\
 c)\\
Every solution base of the solution from (b) is optimal.\\
 \\
\textbf{Task 6}\\
If there is a a cost function for the solution of node n from a graph $G=(V,E)$ recursively like, \\
$C_G(n)=F[E(n),C_G(n_1),C_G(n_2),...,C_G(n_k)]$\\
and we call it recursive cost function.\\
n1,n2...nk is the successor of n.\\
E(n) is a local properties of node n.\\
F is a function to show how the local properties of n and the cost of the direct successor of n will be changed.\\ 
\\
\textbf{Task 7}\\
a)\\
I choose state-space graph (OR graph) to represent, because the problem is hard to reduction.\\
b)\\
I define the information of nodes is weigh s of one package and the objects it take.\\
define the operation of edges is put a object to the bin.\\
c)\\
when one solution is valid, the search return to the root, the dead ends is when the weigh of bin equal or  bigger than 20.\\
d)\\
the cost of edges is choose an object weigh x, S-X is min, S is the weigh package can take.\\
e)\\
package S is 20,\\
let O =\{all items\}\\
let S=\{\}\\
sort O in decreasing order.\\
Loop until O is empty.\\
   choose next item i from O,\\
   if S-i>=0, put it to S,\\
   if all items in O let S-O<0, put S to S', empty S, create new package S recover 20.\\
f)\\
see weng-115131-ponteleev-115151-binh-114910-sa-lab4.py\\
g)\\
$[[16, 4], [15, 1], [13, 7], [11, 9], [7, 6]]$\\ 

\end{document}
